In conventional networks, various routing techniques may be used to transport data packets through the network. There may be multiple paths to transport the data packets between two nodes of the network. The network may be configured to split the traffic among these multiple paths. For example, a multipath routing technique may be used to determine how the traffic will be split among the multiple paths in the network. Exemplary multipath routing techniques may include Weighted Cost MultiPath (WCMP) routing and Equal Cost MultiPath (ECMP) routing. WCMP routing technique may distribute the traffic among available paths based on a set of pre-determined ratios. To deal with uneven path capacities due to asymmetric connectivity among network switches, the routing protocols may set up WCMP groups on the switches for weighted traffic distribution among the multipath paths. If the pre-determined ratios are equal, the WCMP routing may be an ECMP routing where the traffic is distributed evenly among the available paths. The ECMP groups set up on the switches may hash the traffic equally among the multiple egress ports comprising an ECMP group.
An ECMP group is formed when the multipath table of a switch in the network contains multiple next-hop addresses for the same destination with equal cost. A WCMP group is formed when the multipath table of a switch in the network contains multiple next-hop addresses for the same destination with varying cost. A hash algorithm may be used to choose one of the next-hop addresses in the ECMP group or the WCMP group to install in the multipath table.
The WCMP groups often need to be updated to adapt to changes in network topologies and traffic demand. In conventional networks, WCMP group updates are very costly, involving many hardware table accesses. Particularly when the multipath table storing WCMP groups is almost full, adding or expanding a single WCMP group requires reducing the size of existing WCMP groups already installed in the multipath table of the switch. The long delay in updating WCMP groups may result in slow route convergence and high traffic loss in networks after failure events. Therefore, a technique is needed to reduce the hardware table access and thus to reduce the processing time of updating WCMP groups on the switches.